package com.wtgroup.demo.mianshi.算法.排序2305;

import java.util.Arrays;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;

/*
 * # 选择排序
 *
 * ## 时间
 * randomArr(100000, 100000, -123)
 * 1. 比较一次交换一次, 14616ms  (selectSort)
 * 2. 只更新索引, 找到最小的索引后再交换, 2620ms  (selectSort3)
 * 3. 二元选择: 2208ms; 100万卡  (selectSort2)
 * 结论: 二元选择一方面由于减少了搜索次数,↓时间,另一方面增加了代码量, ↑时间; 总的来说只更新索引的普通选择要简单直观.
 *
 *
 * ## 循环次数
 * MyUtils.randomArr(20, 10, -123)
 * - 二元选择72次
 * - 普通190次
 *
 * ## 稳定性
 * 不稳定
 * 例如, 序列5 8 5 2 9， 这个在执行选择排序的时候，第一遍，肯定会将array[0]=5，交换到2所在的位置，也就是 2 8 5 5 9. 这样第一个5跑到第二5后面去了.
 *
 */
public class SelectSort {
	// 2017年9月24日 下午9:12:46 Nisus
	public static void main(String[] args) {
		/*
		 * int[] arr = MyUtils.randomArr(30, 100, -123);
		 * System.out.println(Arrays.toString(arr));
		 * // selectSort(arr);
		 * selectSort2(arr);
		 * System.out.println(Arrays.toString(arr));
		 */


		int[] arr = RandomUtil.randomArray(50_0000, 0, 1000, 123);
		Tools.time(() -> {
			int[] copy = Arrays.copyOf(arr, arr.length);
			Tools.time("sort1", () -> {
				selectSort(copy);
			});
		});

		Tools.time(() -> {
			int[] copy = Arrays.copyOf(arr, arr.length);
			Tools.time("sort3", () -> {
				selectSort3(copy);
			});
		});

	}

	/* 选择排序: 升序 */
	// int//
	public static void selectSort(int[] arr) {
		// int count = 0;
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[i] > arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
				// count++;
			}
		}
		// System.out.println(count);
	}

	/*
	 * 二元选择排序
	 */
	// 简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：
	// 遍历, 找到最大值甩到最末尾, 最小值甩到最开始, 下次循环时, 首尾部分砍掉不用再搜索了 --减少一半搜索次数
	// [1, 1, 3, 3, 4, 4, (7), 6, (5), 6, 5, 7, 7, (5), 8, 8, 8, 8, 8, 9] i=5时
	// [1, 1, 3, 3, 4, 4, 5, 6, 7, 6, 5, 7, 7, 7, 8, 8, 8, 8, 8, 9] i=6时
	// 交换之后, 5就少了一个...
	// 当first和最大值重合或者last和最小值重合, 基本就会出现数值丢失的情况
	// 降序时,当遍历区间首位恰好就是最小值或者末位恰好就是最大值的时候, 楼主的代码基本就会出bug了,
	// ... (2), 6, (9), 8, 5, (4), ...
	// i位2, 也是min.
	// 首->max: 2, 6, 2, 8, 5, 4
	// 末->min: 4, 6, 2, 8, 5, 4
	// max->首: 9, 6, 2, 8, 5, 4
	// min->末: 9, 6, 2, 8, 5, 2
	// 到这一步, 不用看顺序, 只需要看数字的值, 已经变了, 多出了一个2! 4却丢失了!!
	/*
	 * tmp = a[i];
	 * a[i] = a[minpos];
	 * a[minpos] = tmp; //先交换其中首位和min, 然后根据max的位置进行下一步操作
	 * if(maxpos==i)
	 * {
	 * tmp = a[n-i-1];
	 * a[n-i-1] = a[minpos];
	 * a[minpos] = tmp;
	 * }
	 * else
	 * {
	 * tmp = a[n-i-1];
	 * a[n-i-1] = a[maxpos];
	 * a[maxpos] = tmp;
	 * }
	 */
	public static void selectSort2(int arr[]) {
		int i, j, min, max;
		int min_value = 0;
		int max_value = 0;
		int n = arr.length;
		// long count = 0;
		for (i = 0; i <= (n - 1) / 2; i++) {
			// 做不超过n/2趟选择排序
			// 分别记录最大和最小关键字记录位置 \ 每次循环更新索引, 一般待遍历区域的首末假设为最大值或最小值位置
			max = i;
			min = i;
			for (j = i + 1; j <= n - 1 - i; j++) {
				if (arr[j] >= arr[max]) { // >= -->保证相等数值中最后面的为最大值, 这样甩到后面去, 能够保证顺序稳定(升序情况下适用)
					max = j;
					continue;
				}
				if (arr[j] < arr[min]) { // 相等数值中最前面的为最小值
					min = j;
				}
				// count++;
			}
			// 该交换操作还可分情况讨论以提高效率
			// 搜索区域的首末, 最大最小值4个数值拿出来, 最小值放大首位...
			// first:i last:n-1-i min max

			if (i == max) {

				max_value = arr[i];
				arr[i] = arr[min];
				arr[min] = arr[n - 1 - i];
				arr[n - 1 - i] = max_value;
			} else if ((n - 1 - i) == min) {
				min_value = arr[n - 1 - i];
				arr[n - 1 - i] = arr[max];
				arr[max] = arr[i];
				arr[i] = min_value;
			} else {
				// 首位不和最大重叠且末尾不和最小重叠
				min_value = arr[min];
				arr[min] = arr[i];
				arr[i] = min_value;

				max_value = arr[max];
				arr[max] = arr[n - 1 - i];
				arr[n - 1 - i] = max_value;
			}
		}
		// System.out.println(count);
	}

	/**
	 * 先只记录最小值所在的位置, 遍历完了再交换
	 *
	 */
	public static void selectSort3(int[] arr) {
		int min_idx = 0; // 初始化最小值位置
		int temp = 0;
		for (int i = 0; i < arr.length - 1; i++) {
			min_idx = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[min_idx] > arr[j]) {
					min_idx = j; // 先只保存最小值所在位置, 暂不做交换
				}
				// count ++;
			}
			temp = arr[min_idx];
			arr[min_idx] = arr[i];
			arr[i] = temp;
		}
		// System.out.println(count);
	}
}
